package com.zjj.algorithm.learning.leetcode.tree;

/**
 * 111. 二叉树的最小深度 简单题
 * <p>
 * 给定一个二叉树，找出其最小深度。
 * <p>
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * <p>
 * 说明：叶子节点是指没有子节点的节点。
 * <p>
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：root = [2,null,3,null,4,null,5,null,6]
 * 输出：5
 *
 * @author zjj_admin
 * @date 2022/11/23 14:06
 */
public class MinimumDepthOfBinaryTree {


    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(2);
        TreeNode node7 = new TreeNode(2);

        /**
         *                       node1
         *               node2           node3
         *           node4  node5      node6
         *                          node7
         */
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = null;
//        node6.left = node7;

        int res = minDepth(node1);
        System.out.println("res = " + res);

        int res2 = maxDepth(node1);
        System.out.println("res2 = " + res2);

    }


    /**
     * 时间
     * 8 ms
     * 击败
     * 50.74%
     * 内存
     * 61.7 MB
     * 击败
     * 6.85%
     *
     * @param root
     * @return
     */
    public static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        //当左右节点都不为 null 时
        if (root.left != null && root.right != null) {
            int len1 = minDepth(root.left);
            int len2 = minDepth(root.right);
            return Math.min(len1, len2) + 1;
        }
        if (root.left != null) {
            return minDepth(root.left) + 1;
        }
        return minDepth(root.right) + 1;
    }


    /**
     * 求叶子节点的最大深度
     *
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        if (root.left != null && root.right != null) {
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
        if (root.left != null) {
            return maxDepth(root.left) + 1;
        }
        return maxDepth(root.right) + 1;
    }


}
